package com.structure.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
 * 请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * Created by sucre on 2015/11/5.
 */
public class FindNumsAppearOnce {
    private static int findOnlyNum(int[] array){
        int result =0;
        for(int i=0;i<array.length;i++){
            result ^=array[i];
        }
        return result;
    }
    private static String findNums(int[] array){
        int result = findOnlyNum(array);
        String binaryResult = Integer.toBinaryString(result);
        int index = binaryResult.length() -(binaryResult.lastIndexOf("1")+1);
        int resultOne = 0;
        int resultOther = 0;
        for(int i=0;i<array.length;i++){
            if(((array[i] >> index) &1) ==1){
                resultOne^=array[i];
            }else{
                resultOther^=array[i];
            }
        }
        return "resultOne:"+resultOne+" resultTwo:"+resultOther;
    }
    //其实使用hash可以更好的实现，能很快的找到各个数字出现的次数
    private static Map<Integer,Integer> getAppearNum(int[] array){
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for (int a:array){
            if(map.containsKey(a)){
                map.put(a,map.get(a)+1);
            }else{
                map.put(a,1);
            }
        }
        return map;
    }

    public static void main(String args[]){
        int[] array ={2,3,6,8,3,2,7,7};
        System.out.print(findNums(array));
        //Map<Integer,Integer> mp = getAppearNum(array);
    }
}
